11352 - Crazy king/11352 (sin comentarios).cpp

   1 #include <iostream>
   2 #include <climits>
   3 #include <queue>
   4
   5 using namespace std;
   6
   7 char g[101][101];
   8
   9 int deltaCol[] = {-2, -1,  1,  2, 2, 1, -1, -2};
  10 int deltaFil[] = {-1, -2, -2, -1, 1, 2,  2,  1};
  11
  12 int rdeltaCol[] = { -1,  0,  1, 1, 1, 0, -1, -1};
  13 int rdeltaFil[] = { -1, -1, -1, 0, 1, 1,  1,  0};
  14
  15 int inicialCol, inicialFil;
  16
  17 char color[101][101];
  18 unsigned int d[101][101];
  19
  20 int m, n; //m filas, n columnas
  21
  22 const int WHITE = 0;
  23 const int GRAY = 1;
  24 const int BLACK = 2;
  25
  26 void bfs(){
  27   memset(color, WHITE, sizeof(color));
  28   for (int i=0; i<=100; ++i) for (int j=0; j<=100; ++j) d[i][j] = UINT_MAX;
  29   color[inicialFil][inicialCol] = GRAY;
  30   d[inicialFil][inicialCol] = 0;
  31   queue< pair<int,int> > q;
  32   q.push(make_pair(inicialFil, inicialCol));
  33   while (!q.empty()){
  34     int fil = q.front().first, col = q.front().second;
  35     if (g[fil][col] == 'B'){
  36       cout << "Minimal possible length of a trip is ";
  37       cout << d[fil][col] << endl;
  38       return;
  39     }
  40     for (int k=0; k<8; ++k){
  41       int tempFil, tempCol;
  42       tempFil = fil + rdeltaFil[k];
  43       tempCol = col + rdeltaCol[k];
  44       if ( (tempFil >= 0) && (tempFil < m) && (tempCol >= 0) && (tempCol < n)){
  45         char c = g[tempFil][tempCol];
  46         if (c != 'Z' && c != 'X'){
  47           if (color[tempFil][tempCol] == WHITE){
  48             color[tempFil][tempCol] = GRAY;
  49             d[tempFil][tempCol] = d[fil][col] + 1;
  50             q.push(make_pair(tempFil, tempCol));
  51           }
  52         }
  53       }
  54     }
  55     q.pop();
  56     color[fil][col] = BLACK;
  57   }
  58   printf("King Peter, you can't go now!\n");
  59 }
  60
  61
  62 int main(){
  63   int casos;
  64   cin >> casos;
  65   while (casos--){
  66     cin >> m >> n;
  67     for (int i=0; i<m; ++i){
  68       for (int j=0; j<n; ++j){
  69         char c;
  70         cin >> c;
  71         g[i][j] = c;
  72         if (c == 'A'){
  73           inicialFil = i;
  74           inicialCol = j;
  75         }
  76       }
  77     }
  78     for (int i=0; i<m; ++i){
  79       for (int j=0; j<n; ++j){
  80         if (g[i][j] == 'Z'){
  81           for (int k=0; k<8; ++k){
  82             int tempFil, tempCol;
  83             tempFil = i + deltaFil[k];
  84             tempCol = j + deltaCol[k];
  85             if (tempFil >= 0 && tempFil <= m && tempCol >=0 && tempCol < n){
  86               char c = g[tempFil][tempCol];
  87               if (c != 'B' && c != 'A' && c != 'Z') g[tempFil][tempCol] = 'X';
  88             }
  89           }
  90         }
  91       }
  92     }
  93     //En este momento, g[i][j] contiene una X si es una casilla atacable
  94     bfs();
  95   }
  96 }